#include <bits/stdc++.h>
using namespace std;

int n, q, ans[100001];
bool type[100001];
vector<int> askL[100001], askR[100001];
string rule[100001], askstr[100001];

struct node
{
    node *next[2];
    int cnt, tag, val;
    node()
    {
        next[0] = nullptr;
        next[1] = nullptr;
        cnt = 0;
        tag = 0;
        val = 0;
    }
};

node *tree = new node();

void push_down(node *p)
{
    if (!p->next[0])
        p->next[0] = new node();
    if (!p->next[1])
        p->next[1] = new node();
    if (p->tag)
    {
        if (!p->next[0]->val)
        {
            p->next[0]->tag += p->tag;
            p->next[0]->cnt += p->tag;
        }
        if (!p->next[1]->val)
        {
            p->next[1]->tag += p->tag;
            p->next[1]->cnt += p->tag;
        }
        p->tag = 0;
    }
}

void update(int x, int val)
{
    node *p = tree;
    for (int dep = 0; dep < rule[x].size(); dep++)
    {
        push_down(p);
        bool bit = rule[x][dep] - '0';
        if (!p->next[bit])
            p->next[bit] = new node();
        p = p->next[bit];
    }
    p->val += val, p->tag += 1, p->cnt += 1;
    return;
}

int query(int x)
{
    node *p = tree;
    for (int dep = 0; dep < 32; dep++)
    {
        push_down(p);
        bool bit = askstr[x][dep] - '0';
        if (!p->next[bit])
            return 0;
        p = p->next[bit];
    }
    return p->cnt;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> q;

    for (int i = 1; i <= n; i++)
    {
        string t;
        cin >> t >> rule[i];
        type[i] = (t == "Add");
    }

    for (int i = 1; i <= q; i++)
    {
        cin >> askstr[i];
        int L, R;
        cin >> L >> R;
        askL[L].push_back(i);
        askR[R].push_back(i);
    }

    for (int i = 1; i <= n; i++)
    {
        update(i, type[i] ? 1 : -1);

        // 处理左端点查询
        for (int idx : askL[i])
            ans[idx] -= query(idx);

        // 处理右端点查询
        for (int idx : askR[i])
            ans[idx] += query(idx);
    }

    // 输出结果
    for (int i = 1; i <= q; i++)
        cout << ans[i] << endl;

    return 0;
}